#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 注意 [1,2,3,4] (左边更长) 的情况
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return vector<int> ();
        vector<int> res;
        queue<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            int levelSize = nodes.size();
            TreeNode* next;
            for (int i=0; i<levelSize; ++i) {
                next = nodes.front(); nodes.pop();
                if (next->left) nodes.push(next->left);
                if (next->right) nodes.push(next->right);
            }  // now next points to the last node in this level
            res.push_back(next->val);
        }
        return res;
    }
};
